package com.uhu.code;

import com.uhu.code.help.TreeNode;

public class Solution124 {

    public static void main(String[] args) {
        Solution124 solution124 = new Solution124();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(solution124.maxPathSum(root));
    }

    int max = -1001;
    public int maxPathSum(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int maxLeft = maxSum(root.left, 0);
        int maxRight = maxSum(root.right, 0);
        max = Math.max(root.val + maxLeft + maxRight, max);
        if(root.left != null) {
            maxPathSum(root.left);
        }
        if(root.right != null) {
            maxPathSum(root.right);
        }
        return max;
    }

    private int maxSum(TreeNode root, int m) {
        if(root == null) {
            return 0;
        }
        m += root.val;
        return Math.max(m, Math.max(maxSum(root.left, m), maxSum(root.right, m)));
    }
}
